package leetcode_acm.leetcode_1;

import sun.reflect.generics.tree.Tree;

import java.util.HashMap;
import java.util.Map;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年03月11日 12:04
 */
public class BuildTree {

    class  TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        public TreeNode(int val) {
            this.val = val;
        }
    }

    private Map<Integer,Integer> memo = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        //1. 将元素->下标存入到memo中
        for (int i = 0; i < inorder.length; i++) {
            memo.put(inorder[i],i);
        }
        //2. 构建根节点
        return construct(inorder,0, inorder.length-1,postorder,0, postorder.length-1);
    }

    private TreeNode construct(int[] inorder,int inBegin,int inEnd,//定义区间[inBegin,inEnd]
                               int[] postOrder,int postBegin,int postEnd){//定义区间[postBegin,postEnd]
        //1. 判断是否越界
        if(inBegin > inEnd){
            return null;
        }
        //2. 如果没有越界,那么计算四个区间
        //2.0 构建根节点
        int rootVal = postOrder[postEnd];
        TreeNode root = new TreeNode(rootVal);
        //查询in区间这个rootVal所在的下标
        Integer rootInIndex = memo.get(rootVal);
        //2.1 左子树的in区间:[inBegin,rootInIndex-1]
        int leftInBegin = inBegin,leftInEnd = rootInIndex-1;
        //2.2 右子树的in区间:[rootInIndex+1,inEnd]
        int rightInBegin = rootInIndex+1,rightInEnd = inEnd;
        //2.3 右子树的post区间
        //先计算出右子树有多少个节点:(inEnd-rootIndex-1)+1
        int rightSize = inEnd-rootInIndex;
        //那么右子树的区间就是:[postEnd-1-rightSize+1,postEnd-1]=>[postEnd-rightSize,postEnd-1]
        int rightPostBegin = postEnd-rightSize,rightPostEnd = postEnd-1;
        //2.4 左子树的post区间:[postBegin,postEnd-rightSize-1]
        int leftPostBegin = postBegin,leftPostEnd = postEnd-rightSize-1;
        //3. 构建左右子树,返回当前节点
        root.left = construct(inorder,leftInBegin,leftInEnd,postOrder,leftPostBegin,leftPostEnd);
        root.right = construct(inorder,rightInBegin,rightInEnd,postOrder,rightPostBegin,rightPostEnd);
        return root;
    }
}
